import java.util.Collection;
import java.util.Set;
import java.util.ArrayList;
import java.util.HashSet;

/**
 * This class will represent a modified linear probing hash table. 
 * The modification is specified in the comments for the put method.
 */
public class HashTable<K,V> {
	
	/**
	 * Constant determining the max load factor
	 */
	private final double MAX_LOAD_FACTOR = 0.71;
	
	/**
	 * Constant determining the initial table size
	 */
	private final int INITIAL_TABLE_SIZE = 11;
	
	/**
	 * Number of elements in the table
	 */
	private int size;
	
	/**
	 * The backing array of this hash table
	 */
	private MapEntry<K,V>[] table;
	
	/**
	 * Initialize the instance variables
	 * Initialize the backing array to the initial size given
	 */
	@SuppressWarnings("unchecked")
	public HashTable() {
		table = new MapEntry[INITIAL_TABLE_SIZE];
		size = 0;
	}
	
	/**
	 * Add the key value pair in the form of a MapEntry
	 * Use the default hash code function for hashing
	 * This is a linear probing hash table so put the entry in the table accordingly
	 * 
	 * Make sure to use the given max load factor for resizing
	 * Also, resize by doubling and adding one. In other words:
	 * 
	 * newSize = (oldSize * 2) + 1
	 *
	 * The load factor should never exceed maxLoadFactor at any point. So if adding this element
	 * will cause the load factor to be exceeded, you should resize BEFORE adding it. Otherwise
	 * do not resize.
	 * 
	 * IMPORTANT Modification: If the given key already exists in the table
	 * then set it as the next entry for the already existing key. This means
	 * that you will never be replacing values in the hashtable, only adding or removing.
	 * This is similar to external chaining
	 * 
	 * @param key This will never be null
	 * @param value This can be null
	 */
	public void put(K key,V value){
		
		if ((size + 1.0)/table.length >= MAX_LOAD_FACTOR){
			resize();
		}
		
		MapEntry<K, V> entry = new MapEntry<K,V>(key,value);
		int hash = Math.abs(key.hashCode()) % table.length;
				
		//easy case: [spot is empty]
		if (table[hash] == null){
			table[hash] = entry;
		}
		
		//spot is removed and key is the same
		if (table[hash].isRemoved() && same(key, table[hash].getKey())){
			table[hash] = entry;
		}
		//spot is removed and key is different
		//need to see if key appears elsewhere before using put
		if (table[hash].isRemoved() && !same(key, table[hash].getKey())){
			//see if key is elsewhere
			for (int i = hash; i < table.length + hash + 1; i++ ){
				//key is elsewhere
				if (table[i % table.length] != null && same(key, table[i % table.length].getKey())){
					putIndex(entry, i % table.length);
				}
			}
			//key was not in table
			table[hash] = entry;
		}
		//spot is occupied and key is the same
		else if(same(key, table[hash].getKey())){
			putIndex(entry, hash);
		}
		
		//spot is occupied by different key
		else if(!same(key, table[hash].getKey())){
			boolean found = false;
			//search to see if at different index
			for (int i = hash; i < table.length + hash + 1; i++ ){
				//key is elsewhere
				//System.out.println("searching for " + key);
				if (table[i % table.length] != null && same(key, table[i % table.length].getKey())){
					//System.out.println("found " + key + " already at " + (i % table.length));
					putIndex(entry, i % table.length);
					found = true;
				}
			}
			//key was not in table; have to find next available index
			//have to use modulus to loop around array
			//System.out.println(key + " not found already in table");
			if (found == false){
				int i = hash;
				while( table[i % table.length] != null && !table[i % table.length].isRemoved()){
					i++;
				}
				//made it to next available index
				putIndex(entry, i % table.length);
			}
		}
		size++;
	}
	
	//additional method for testing
	public MapEntry<K,V> putTest(K key, V value){
		put(key, value);
		return new MapEntry<K, V>(key, value);
	}

	
	//helper method for resizing    NEEDS TO BE FIXED...
	@SuppressWarnings("unchecked")
	public void resize(){
		MapEntry<K,V>[] beforeResize = table;
		table = new MapEntry[(beforeResize.length * 2) + 1];
		System.out.println("table length is now " + table.length);
		
		//put entries from old table into new one
		for(int i = 0; i < beforeResize.length; i++){
			//index has an entry
			if ( beforeResize[i] != null && !beforeResize[i].isRemoved()){
				//put entry at i into new table
				MapEntry<K,V> temp = beforeResize[i];
				int tempHash = temp.getKey().hashCode() % table.length;
				if (table[tempHash] == null){
					table[tempHash] = temp;
				}
				else{
					for( int j = tempHash; j < table.length + tempHash + 1; i++){
						if ( table[j % table.length] == null){
							table[j % table.length] = temp;
						}
					}
				}
			}
		}
		
		
	}
	
	public boolean same(K key, K tempKey){
		return(key.equals(tempKey));
	}
	
	
	//helper method for put
	//puts map entry at given index
	public void putIndex(MapEntry<K,V> m, int i){
		if (table[i] == null){
			table[i] = m;
		}
		
		else if (table[i].isRemoved()){
			table[i] = m;
		}
		else{
			MapEntry<K,V> temp = table[i];
			while(temp.getNext() != null){
				temp = temp.getNext();
			}
			temp.setNext(m);
		}
	}
	
	
	/**
	 * Remove the entry with the given key.
	 * 
	 * If there are multiple entries with the same key then remove the last one
	 * 
	 * @param key
	 * @return The value associated with the key removed
	 */
	public V remove(K key){
	
		V removed = null;
		
		for (int i = 0; i < table.length; i++){
			if(table[i] != null && !table[i].isRemoved()){
				//case 1: only one instance of key
				if (table[i].getNext() == null){
					table[i].setRemoved(true);
					return(table[i].getValue());
				}
				//case 2: more instances
				else{
					MapEntry<K,V> previous = table[i];
					MapEntry<K,V> temp = table[i];
					while ( temp.getNext() != null){
						previous = temp;
						temp = temp.getNext();
					}
					removed = temp.getValue();
					previous.setNext(null);
					return removed;	
				}	
			}
		}
		//key not in table
		return removed;
	}
	
	/**
	 * Checks whether an entry with the given key exists in the hash table
	 * 
	 * @param key
	 * @return
	 */
	public boolean contains(K key){//works
		Set<K> keys = keySet();
		for (K k : keys){
			if (key.equals(k)){
				return(true);
			}
		}
		return false;
	}
	
	/**
	 * Return a collection of all the values
	 * 
	 * We recommend using an ArrayList here
	 *
	 * @return 
	 */
	public Collection<V> values(){//FIX ME
		ArrayList<V> values = new ArrayList<V>();
		for(int i = 0; i < table.length; i++){
			
			//System.out.println(i);
			if (table[i] != null){
				
				MapEntry<K,V> temp = table[i];
				
				while (temp.getNext() != null){
					if (temp.getValue() != null && !temp.isRemoved()){
						//System.out.println("temp " + temp.getValue());
						//System.out.println("next " + temp.getNext().getValue());
						values.add(temp.getValue());
					}
					temp = temp.getNext();
				}
			}
		}
		return values;
	}
	
	/**
	 * Return a set of all the distinct keys
	 * 
	 * We recommend using a HashSet here
	 * 
	 * Note that the map can contain multiple entries with the same key
	 * 
	 * @return
	 */
	public Set<K> keySet(){//works
		HashSet<K> keys = new HashSet<K>();
		for(int i = 0; i < table.length; i++){
			if (table[i] != null && !table[i].isRemoved()){
				keys.add(table[i].getKey());
			}
		}
		return keys;
	}
	
	/**
	 * Return the number of values associated with one key
	 * Return -1 if the key does not exist in this table
	 * @param key
	 * @return
	 */
	public int keyValues(K key){
		if (!contains(key)){
			return -1;
		}
		else{
			return 3; //CODE THIS
		}
	}
	
	/**
	 * Return a set of all the unique key-value entries
	 * 
	 * Note that two map entries with both the same key and value
	 * could exist in the map.
	 * 
	 * @return
	 */
	public Set<MapEntry<K,V>> entrySet(){
		return null;
	}
	
	/**
	 * Clears the hash table
	 */
	@SuppressWarnings("unchecked")
	public void clear(){
		table = new MapEntry[11];
		size = 0;
	}
	
	/*
	 * The following methods will be used for grading purposes do not modify them
	 */
	
	public int size(){
		return size;
	}
	
	public void setSize(int size) {
		this.size = size;
	}
	
	public MapEntry<K, V>[] getTable() {
		return table;
	}
	
	public void setTable(MapEntry<K, V>[] table) {
		this.table = table;
	}
	
}
